Assume s is a string of lower case characters.
Write a program that prints the longest substring of s in which the letters occur in alphabetical order. For example, if s = 'azcbobobegghakl', then your program should print
Longest substring in alphabetical order is: beggh
In the case of ties, print the first substring. For example, if s = 'abcbcd', then your program should print
Longest substring in alphabetical order is: abc
For problems such as these, do not include raw_input statements or define the variable s in any way. Our automated testing will provide a value of s for you - so the code you submit in the following box should assume s is already defined. If you are confused by this instruction, please review L4 Problems 10 and 11 before you begin this problem set.
Note: This problem is fairly challenging. We encourage you to work smart. If you've spent more than a few hours on this problem, we suggest that you move on to a different part of the course. If you have time, come back to this problem after you've had a break and cleared your head.
In [ ]:
from itertools import count
def find_substring(input_string):
maxsubstr = input_string[0:0]
for start in range(len(input_string)):
for end in count(start+len(maxsubstr)+1):
substr = input_string[start:end]
if len(substr)!=(end - start):
break
if sorted(substr) == list(substr):
maxsubstr = substr
return maxsubstr
s = raw_input("Please input a String:")
log_substr = find_substring(s)
print ("Longest substring in alphabetical order is:"+log_substr)
In [4]:
from compiler.ast import flatten
In [5]:
def Ngram_s(s, length):
return map(lambda idx:s[idx:idx+length], xrange(0, len(s)-length+1) )
def alpha_2_id(s):
alpha_dict = {'a': 1, 'b': 2, 'c': 3, 'd': 4, 'e': 5,\
'f': 6, 'g': 7, 'h': 8, 'i': 9, 'j': 10, 'k': 11,\
'l': 12, 'm': 13, 'n': 14, 'o': 15, 'p': 16, 'q': 17,\
'r': 18, 's': 19, 't': 20, 'u': 21, 'v': 22, 'w': 23,\
'x': 24, 'y': 25, 'z': 26}
id_list = map(lambda char: alpha_dict[char], list(s))
return id_list
def is_alpha_order(id_list):
is_alpha_order = 0
sorted_id_list = sorted(id_list)
if sorted_id_list == id_list: is_alpha_order = 1
return (id_list, len(id_list), is_alpha_order)
def id_list_2_alpha_list(id_list):
id_dict = {1: 'a', 2: 'b', 3: 'c', 4: 'd', 5: 'e', 6: 'f',\
7: 'g', 8: 'h', 9: 'i', 10: 'j', 11: 'k', 12: 'l',\
13: 'm', 14: 'n', 15: 'o', 16: 'p', 17: 'q', 18: 'r',\
19: 's', 20: 't', 21: 'u', 22: 'v', 23: 'w', 24: 'x',\
25: 'y', 26: 'z'}
alpha_list = map(lambda id: id_dict[id], id_list)
alpha_string = "".join(alpha_list)
return alpha_string
"""
alpha_dict = {'a': 1, 'b': 2, 'c': 3, 'd': 4, 'e': 5,\
'f': 6, 'g': 7, 'h': 8, 'i': 9, 'j': 10, 'k': 11,\
'l': 12, 'm': 13, 'n': 14, 'o': 15, 'p': 16, 'q': 17,\
'r': 18, 's': 19, 't': 20, 'u': 21, 'v': 22, 'w': 23,\
'x': 24, 'y': 25, 'z': 26}
id_dict = {}
for k, v in alpha_dict.iteritems():
id_dict[v] = k
print id_dict
"""
Out[5]:
In [7]:
s = 'onvorzvkcttm'
all_possible_substring_list = map(lambda length: Ngram_s(s, length), xrange(1, len(s)+1))
#print "all_possible_substring_list:%s" % all_possible_substring_list
sorted_all_possible_substring_list = sorted(list(set(flatten(all_possible_substring_list))), reverse=True)
#print "sorted_all_possible_substring_list:%s" % sorted_all_possible_substring_list
id_2d_list = map(lambda substring: alpha_2_id(substring), sorted_all_possible_substring_list)
#print "id_2d_list:%s" % id_2d_list
id_list_and_length_and_is_alpha_order_trigram_tuple_list = map(
lambda id_list: is_alpha_order(id_list),
id_2d_list)
#print "id_list_and_length_and_is_alpha_order_trigram_tuple_list:%s" % id_list_and_length_and_is_alpha_order_trigram_tuple_list
alpha_order_tuple_list = filter(lambda trigram_tuple: trigram_tuple[2] == 1, id_list_and_length_and_is_alpha_order_trigram_tuple_list)
#print "len(alpha_order_tuple_list):%s" % len(alpha_order_tuple_list)
result_tuple_list = map(
lambda alpha_order_tuple:
(alpha_order_tuple[1], id_list_2_alpha_list(id_list = alpha_order_tuple[0])),
alpha_order_tuple_list)
#print "result_tuple_list:%s" % result_tuple_list
sorted_result_tuple_list = sorted(result_tuple_list, key=lambda result_tuple: result_tuple[0], reverse=True)
#print "Longest substring in alphabetical order is: %s" % max_len_alpah_order_length
max_len_alpha_string = sorted_result_tuple_list[0][1]
print "Longest substring in alphabetical order is: %s" % max_len_alpha_string